1. Field of the Invention
The present invention relates generally to a system for the compression and decompression of digitized imagery which is useful both for transmission through narrow bandwidth communications channels and efficient archival storage in a data retrieval system. More specifically, to minimize computational complexity and memory usage, the system described herein uses lifting to implement its wavelet transforms and performs embedded coefficient coding in-place, i.e., without reorganizing the data into traditional subbands. By processing the data in-place, data movement is minimized in both the encoder and decoder and scratch memory requirements are greatly reduced.
2. Brief Description of the Related Art
Digital data compression systems are useful to reduce the number of bits required to represent a signal in digital form. Digital data is typically compressed to either facilitate transmission of the signal through a limited-bandwidth communications channel or to reduce the amount of memory needed to store that signal on some archival media such as a computer hard disk. Digital data compression can be achieved using either lossless or lossy coding techniques. Lossless coding involves only the extraction of statistical redundancy from the signal, and, thus, the amount of compression possible is signal dependent with compression ratios of 2:1 common for natural images.
To get higher levels of compression or to code the signal at a fixed bit rate, some distortion must be accepted in the reconstructed signal, resulting in a loss of information when the signal is passed through the complete encoding and decoding system. The goal of a good lossy coding system, then, is to minimize the distortion introduced into the signal at all of the bit rates for which the system is designed to operate, e.g., attaining the best rate-distortion performance possible.
A variety of image compression algorithms and systems have been proposed in recent years. Many of the algorithms with the best rate-distortion performance such as the Joint Photographics Experts Group (JPEG), described in xe2x80x9cOverview of the JPEG (ISO/CCITT) Still Image Compressionxe2x80x9d by G. K. Wallace in SPIE, Vol. 1244, Image Proc. Algorithms and Techniques, 1990, pp. 220-233, and Zerotree Coders, described in xe2x80x9cEmbedded Image Coding Using Zerotrees of Wavelet Coefficientsxe2x80x9d by J. M. Shapiro in IEEE Trans. On Signal Processing, Vol. 41, No. 12, December 1993, pp. 3445-3462, the disclosures of which are herein incorporated by reference, use transforms to decorrelate image pixels before coding of the data. The JPEG standard relies on a block-based discrete cosine transform (DCT). A coding algorithm based on the wavelet-packet transform showing improved rate-distortion performance for difficult images is described in xe2x80x9cWavelet Packet-Based Image Coding Using Joint Space-Frequency Quantizationxe2x80x9d by Z. Xiong, K. Ramchandran and M. T. Orchard in Proc. Int. Conf On Image Proc., November 1994, Austin, Tex., pp. 324-328, the disclosure of which is herein incorporated by reference.
The zerotree coder uses a multiresolutional wavelet transform and takes advantage of the correlation between insignificant coefficients at different scales. U.S. Pat. No. 5,315,670, to James M. Shapiro, entitled xe2x80x9cDigital Data Compression System Including Zerotree Coefficient Codingxe2x80x9d discloses a digital data processing system which includes means for generating a tree structure of data representative coefficients with the tree structure having multiple paths from coefficients generated at a level of coarsest information to coefficients generated at a level of relatively finer information. The coefficients are evaluated to distinguish between significant and insignificant coefficients. Means are also included for generating a dedicated symbol representing a related association of insignificant coefficients within the tree structure, from a root coefficient of the tree structure to a set of end coefficients of the tree structure. The symbol represents that neither the root coefficient of the tree structure nor any descendant of the root coefficient has a magnitude greater than a given reference level. A coefficient is considered to be insignificant and a xe2x80x9croot of a zerotreexe2x80x9d, whereby all descendants are predictably insignificant, if (a) the coefficient has an insignificant magnitude, (b) the coefficient is not the descendant of a root from a coarser level, and (c) all the descendants of the coefficient at finer levels have insignificant magnitudes. A coefficient found to be a zerotree root is coded with a dedicated symbol which is eventually processed by an entropy coder.
Other embedded compression algorithms that rely on inter-subband redundancy extraction are detailed in articles entitled xe2x80x9cCREW: Compression with Reversible Embedded Wavelets,xe2x80x9d by A. Zandi, J. D. Allen, E. L. Schwartz, and M. Boliek, Proc. Data Compression Conference, 1995, pp. 212-221; and xe2x80x9cAn Image Multiresolution Representation for Lossless and Lossy Compression,xe2x80x9d by A. Said and W. A. Pearlman, IEEE Trans. on Image Proc., Vol. 5, No. 9, September 1996, pp. 1303-1310 (detailing SPIHTxe2x80x94Set Partitioning in Hierarchical Trees); and xe2x80x9cMultirate 3-D Subband Coding of Video,xe2x80x9d by D. Taubman and A. Zakhor, IEEE Trans. on Image Proc., Vol.3, No. 5, September 1994, pp. 572-588 (detailing LZCxe2x80x94Layered zero coding), the disclosures of which are herein incorporated by reference.
Fundamental to all of these compression algorithms is the wavelet transform. An infinite number of different wavelets exist, but as detailed in an article entitled xe2x80x9cLow Bit-Rate Design Considerations for Wavelet-Based Image Coding,xe2x80x9d by M. Lightstone and E. Majani, Multidimensional Systems and Signal Proc., 8, pp. 111-128 (1997), the disclosure of which is herein incorporated by reference, short, biorthogonal wavelets tend to provide the best results for image and video compression. Such wavelets are typically constructed using multirate digital filter banks. A wavelet coefficient mapping is created by iteratively decomposing the low-low band (low vertical frequency, low horizontal frequency), where the wavelet coefficients are organized in distinct dyadic subbands ranging from low frequency in the upper left-hand corner to high in the lower right. In the absence of coefficient quantization, i.e., with lossless compression, the original image can be reconstructed by iteratively applying the inverse wavelet transform.
In view of the foregoing, there is a need for a compression system that provides a more efficient and flexible way of correlating between insignificant coefficients at different scales incorporated into a zerotree coder.
It is an object of the present invention to provide a system that relies on lifted wavelets to perform analysis and synthesis, and processes the coefficients that result from such transforms in-place, using algebraically-calculated parent-child zerotree relationships rather than the memory-consuming linked lists previously known.
It is further an object of the present invention to apply the efficient zerotree indexing scheme to other embedded compression algorithms.
These and other objects are accomplished by the present invention that includes a system for compressing digital data comprising an image, the image collected for electronic manipulation, means for converting the image using lifted wavelet transforms, and, means for applying the converted image.
The present invention further includes a method for converting an image, comprising the steps of acquiring an image, storing the acquired image as a data array in a memory system, progressively replacing pixel elements of the stored data array with transform coefficient elements through the lifted transformation, scanning the transform coefficients to create an embedded symbol stream, and, losslessly encoding the embedded symbol stream to create an embedded bit stream.
Additionally, the present invention includes a digital data compression and decompression system comprising the steps of encoding and decoding individual regions of an image controlled through a simple indexing scheme.